#ifndef CACHE_SET_LRU_H
#define CACHE_SET_LRU_H


#include "AssocContainer.h"
#include "CacheLineLRU.hpp"
#include "CacheSet.hpp"
#include "Directory.h"

#include "cache_types.h"

#include <vector>
#include <iostream>

#define listInsert(l, i)         \
   do {                           \
      if (l) {                     \
         i->setNext(l);             \
         i->setPrev(l->getPrev());  \
         l->getPrev()->setNext(i);  \
         l->setPrev(i);             \
      } else {                     \
         i->setPrev(i);             \
         i->setNext(i);             \
         l = i;                     \
      }                            \
   } while (0);\

#define listHeadRemove(i)                      \
   do {                                        \
      if (i->getNext() != i) {                 \
          i->getPrev()->setNext(i->getNext()); \
          i->getNext()->setPrev(i->getPrev()); \
          i=i->getNext();                      \
      } else {                                 \
          i=NULL;                              \
      }\
   } while (0);\


#define listRemove(i)    \
 do {                     \
     i->getPrev()->setNext(i->getNext());  \
     i->getNext()->setPrev(i->getPrev());  \
 }while (0);\



#define listEmpty(l) (l == NULL)

#define listSearch(l, a, w)        \
   do {                            \
      int i=0;                     \
      w = l->getNext();            \
      do {                         \
         if (a == w->getAddress()) \
         break;                    \
         w = w->getNext();         \
         i++;                      \
      } while (w != l && i<this->_size);  \
   } while (0);


template <typename TData>
class CacheSetLRU : public CacheSet<TData> {
    public:
        CacheSetLRU ( uint16_t size,bool directory,uint32_t pagesInDirectory)
            : CacheSet<TData> (size)
        {
            this->_lines = new CacheLineLRU<TData>[size];
            for (uint16_t i = 0; i < size; i++) {
                _lines[i]._line = new CacheLine<TData>(directory,pagesInDirectory);
            }
            this->reset();
        }

        ~CacheSetLRU()
        {
            for (uint16_t i = 0; i < this->_size; i++) {
                delete _lines[i]._line;
            }
            delete [] this->_lines;
        }

        bool
        invalidate (address_t address)
        {
                CacheLineLRU<TData> * where;

                if (listEmpty(this->_top))
                    return false;
                else if (address == this->_top->getAddress()) {
                    where = this->_top;
                    this->_top->resetAllDirectory();
                    listHeadRemove(this->_top);
                    if (!listEmpty(this->_top))
                        this->_top = this->_top->getNext();
                    listInsert(this->_empty, where);

                    return true;
                }

                listSearch(this->_top, address, where);

                if (where == this->_top)
                    return false;
                else {
                    //this->result._line = where->_line;
                    this->_top->resetAllDirectory();
                    listRemove(where);
                    listInsert(this->_empty, where);

                    return true;
                }
          }

        uint32_t
            flushDirEntry (address_t address,uint32_t thread,uint32_t page)
            {
                CacheLineLRU<TData> * where;
                uint32_t count=0;

                if (listEmpty(this->_top))
                    return 0;
                else if (address == this->_top->getAddress()) {
                    where = this->_top;
                    // reset directory entry
                    this->_top->resetDirectory(thread,page);
                    count=this->_top->countDirectory();
                    if (count==0)
                        listHeadRemove(this->_top);
                    if (!listEmpty(this->_top))
                        this->_top = this->_top->getNext();
                    listInsert(this->_empty, where);

                    return count;
                }

                listSearch(this->_top, address, where);

                if (where == this->_top)
                    return 0;
                else {
                    // reset directory entry
                    this->_top->resetDirectory(thread,page);
                    count=this->_top->countDirectory();
                    if (count==0)
                        listHeadRemove(this->_top);
                    listInsert(this->_empty, where);

                    return count;
                }
            }



        bool
            flush (address_t address)
            {
                CacheLineLRU<TData> * where;

                if (listEmpty(this->_top))
                    return false;
                else if (address == this->_top->getAddress()) {
                    where = this->_top;
                    //this->result.line = where->_line;
                    this->_top->resetAllDirectory();
                    listHeadRemove(this->_top);
                    if (!listEmpty(this->_top))
                        this->_top = this->_top->getNext();
                    listInsert(this->_empty, where);

                    return true;
                }

                listSearch(this->_top, address, where);

                if (where == this->_top)
                    return false;
                else {
                    //this->result.line = where->_line;
                    this->_top->resetAllDirectory();
                    listRemove(where);
                    listInsert(this->_empty, where);

                    return true;
                }
            }


        void
            flush ()
            {
                CacheLineLRU<TData> * where = this->_top;
                int i=0;
                if (!listEmpty(this->_top)) {
                    do {
                        where = this->_top;
                        where->setAddress(0);
                        listHeadRemove(this->_top);
                        if (!listEmpty(this->_top))
                            this->_top = this->_top->getNext();
                        listInsert(this->_empty, where);
                        i++;

                    } while (!listEmpty(this->_top) && i<this->_size);
                }
                this->reset();
            }


        void
            print () const
            {
                CacheLineLRU<TData> * l = this->_top;

                if (!listEmpty(l)) {
                    do {
                        std::cout << "<TOP>   ADDR: " << std::hex << l->getAddress() << std::endl;
                        l = l->getNext();
                    } while (l != this->_top);
                }

                l = this->_empty;
                if (!listEmpty(l)) {
                    do {
                        std::cout << "<EMPTY> ADDR: " << std::hex << l->getAddress() << std::endl;
                        l = l->getNext();
                    } while (l != this->_empty);
                }
            }

        //
        // PRIVATE FUNCTIONS
        //


        void
            reset ()
            {
                this->_top   = NULL;
                this->_empty = this->_lines;

                for (int i = 1; i < (this->_size - 1); i++) {
                    this->_empty[i].setPrev(&this->_empty[i-1]);
                    this->_empty[i].setNext(&this->_empty[i+1]);
                }

                this->_empty[0].setNext(&this->_empty[1]);
                this->_empty[0].setPrev(&this->_empty[this->_size-1]);

                this->_empty[this->_size-1].setNext(&this->_empty[0]);
                this->_empty[this->_size-1].setPrev(&this->_empty[this->_size-2]);
            }

        CacheAccess
            find (address_t addr)
            {
                CacheLineLRU<TData> * where;
                CacheAccess result;

                if (listEmpty(this->_top)) {
                    result = CACHE_MISS_NEW;
                } else if (addr == this->_top->getAddress()) {
                    // HIT on the top of the stack
                    result = CACHE_HIT_TOP;
                } else {
                    // Is it a HIT?
                    listSearch(this->_top, addr, where);
                    if (where == this->_top) { // NO
                        if (listEmpty(this->_empty)) {
                            where = this->_top->getPrev();
                            if (where->isDirty()) {
                                result = CACHE_MISS_EVICT_DIRTY;
                            } else {
                                result = CACHE_MISS_EVICT;
                            }
                        } else {
                            result = CACHE_MISS_NEW;
                        }
                    } else {                  // YES
                        result = CACHE_HIT_PUSH;
                    }
                }

                return result;
            }

        CacheAccess
            read (address_t addr, address_t & evict,Directory & dirEvict,
                    Directory & dirEntry,TData & data, uint32_t thread,uint32_t dirPage)
            {
                CacheLineLRU<TData> * where;
                CacheAccess result;

                if (listEmpty(this->_top)) {
                    where = this->_empty;
                    listHeadRemove(this->_empty);
                    this->_empty = where->getNext();
                    listInsert(this->_top, where);
                    this->_top = where;
                    where->setDirectory(thread,dirPage);
                    where->setAddress(addr);
                    result = CACHE_MISS_NEW;
                } else if (addr == this->_top->getAddress()) {
                    // HIT on the top of the stack
                    result = CACHE_HIT_TOP;
                    this->_top->setDirectory(thread,dirPage);
                    data=this->_top->getData();
                } else {
                    // Is it a HIT?
                    listSearch(this->_top, addr, where);

                    if (where == this->_top) { // NO
                        if (listEmpty(this->_empty)) {
                            where = this->_top->getPrev();
                            where->_line->getDirEntry(dirEvict);
                            evict = where->_line->getAddress();
                            if (where->isDirty()) {
                                result = CACHE_MISS_EVICT_DIRTY;
                            } else {
                                result = CACHE_MISS_EVICT;
                            }
                            listRemove(where);
                        } else {
                            where = this->_empty;
                            listHeadRemove(this->_empty);
                            if (!listEmpty(this->_empty))
                                this->_empty = where->getNext();
                            result = CACHE_MISS_NEW;
                        }

                        where->setAddress(addr);
                        where->resetAllDirectory();
                        where->setDirectory(thread,dirPage);
                        listInsert(this->_top, where);
                        this->_top = where;
                    } else {                  // YES
                        listRemove(where);
                        listInsert(this->_top, where);
                        this->_top = where;
                        data=this->_top->getData();
                        this->_top->setDirectory(thread,dirPage);
                        result = CACHE_HIT_PUSH;
                    }
                }

                return result;
            }



        CacheAccess
            writeAllocate (address_t addr, address_t & evict,
                    uint32_t thread,TData data,uint32_t dirPage)
            {
                CacheLineLRU<TData> * where;
                CacheAccess result;

                if (listEmpty(this->_top)) {
                    where = this->_empty;
                    listHeadRemove(this->_empty);
                    this->_empty = where->getNext();
                    listInsert(this->_top, where);
                    where->setDirectory(thread,dirPage);
                    /* Change the pointer and register the new address */
                    where->setDirty();
                    where->setAddress(addr);
                    where->setData(data);
                    result = CACHE_MISS_NEW;
                } else if (addr == this->_top->getAddress()) {
                    // HIT on the top of the stack
                    result = CACHE_HIT_TOP;
                    this->_top->setDirectory(thread,dirPage);
                    this->_top->setData(data);
                } else {
                    // Is it a HIT?
                    listSearch(this->_top, addr, where);

                    if (where == this->_top) { // NO
                        if (listEmpty(this->_empty)) {
                            where = this->_top->getPrev();
                            if (where->isDirty()) {
                                evict = where->_line->getAddress();
                                result = CACHE_MISS_EVICT_DIRTY;
                            } else {
                                result = CACHE_MISS_EVICT;
                            }
                            listRemove(where);
                        } else {
                            where = this->_empty;
                            listHeadRemove(this->_empty);
                            if (!listEmpty(this->_empty))
                                this->_empty = where->getNext();
                            result = CACHE_MISS_NEW;
                        }

                        where->setAddress(addr);
                        where->setDirty();
                        where->setData(data);
                        listInsert(this->_top, where);
                        this->_top = where;
                        this->_top->setDirectory(thread,dirPage);
                    } else {                  // YES
                        listRemove(where);
                        where->setDirty();
                        where->setData(data);
                        listInsert(this->_top, where);
                        this->_top = where;
                        this->_top->setDirectory(thread,dirPage);
                        result = CACHE_HIT_PUSH;
                    }
                }

                return result;
            }



        CacheAccess
            writeNonAllocate (address_t  addr,uint32_t thread,
                    TData data,uint32_t dirPage)
            {
                CacheLineLRU<TData> * where;
                CacheAccess result;

                if (listEmpty(this->_top)) {
                    result = CACHE_MISS_NEW;
                } else if (addr == this->_top->getAddress()) {
                    // HIT on the top of the stack
                    result = CACHE_HIT_TOP;
                    this->_top->setDirectory(thread,dirPage);
                    this->_top->setData(data);
                } else {
                    // Is it a HIT?
                    listSearch(this->_top, addr, where);

                    if (where == this->_top) { // NO
                        if (listEmpty(this->_empty))
                            result = CACHE_MISS_EVICT;
                        else
                            result = CACHE_MISS_NEW;
                    } else {                  // YES
                        listRemove(where);
                        where->setDirty();
                        listInsert(this->_top, where);
                        this->_top = where;
                        this->_top->setDirectory(thread,dirPage);
                        this->_top->setData(data);
                        result = CACHE_HIT_PUSH;
                    }
                }

                return result;
            }

    protected:
        CacheLineLRU<TData> * _top;
        CacheLineLRU<TData> * _empty;
        CacheLineLRU<TData> * _lines;
};

#endif
